package com.dyz.leetcode._05_sort;

public class _jianzhi51_ReversePairs {
    //O(n^2)
     public int reversePairs1(int[] nums) {
         int res = 0;
         for(int i = 0; i<nums.length;i++){
             for(int j = i+1; j< nums.length; j++){
                 if(nums[j]<nums[i]){
                     res++;
                 }
             }
         }
     return res++;
     }

    public int reversePairs(int[] nums) {
        int[] copy = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[nums.length];
        return reversePairs(copy, 0, nums.length-1, temp);


    }

    private int reversePairs(int[] nums, int left, int right, int[] temp) {
         if(left>=right){
             return 0;
         }
         int mid = (left+right)/2;

         int leftReversePairs = reversePairs(nums, left, mid, temp);
         int rightReversePairs = reversePairs(nums, mid+1, right, temp);

         //合并
        int mergeReverse = mergeAndCountReversePairs(nums, left, mid, right, temp);
        return  leftReversePairs+rightReversePairs+mergeReverse;
    }

    private int mergeAndCountReversePairs(int[] nums, int left, int mid, int right, int[] temp) {
         for(int i=left; i<=right; i++){
             temp[i] = nums[i];
         }
         int count = 0;
         int i = left;
         int j = mid+1;
         for(int k=left; k<=right; k++){
             if (i == mid + 1) { // 左边没有元素，右边有元素
                 nums[k] = temp[j++];
             } else if (j == right + 1) { // 左边有元素，右边没有元素
                 nums[k] = temp[i++];
             } else if (temp[i] <= temp[j]) {
                 nums[k] = temp[i++];
             } else { // tmp[i] > tmp[j]
                 nums[k] = nums[j++];
                 // 计算 temp[j] 的逆序对
                 count += mid - i + 1;
             }
         }
        return count;
    }
}
